/*
 * Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following is not:
    1
   / \
  2   2
   \   \
   3    3
 */
package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.List;

public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null)
            return true;
        
        boolean fin = false;
        List<TreeNode> p = new ArrayList<TreeNode>();
        List<TreeNode> children = new ArrayList<TreeNode>();
        p.add(root);
        
        while(!fin)
        {
            fin = true;
            for(TreeNode n : p)
            {
                fin = false;
                if(n.left == null)
                    children.add(new TreeNode(Integer.MIN_VALUE));
                else
                    children.add(n.left);
                if(n.right == null)
                    children.add(new TreeNode(Integer.MIN_VALUE));
                else
                    children.add(n.right);
            }
            int l = children.size();
            for(int i = 0; i < l/2; i++)
            {
                if(children.get(i).val != children.get(l-i-1).val)
                    return false;
            }
            p.clear();
            for(int i = 0; i < l; i++)
                if(children.get(i).val != Integer.MIN_VALUE)
                    p.add(children.get(i));
            children.clear();
        }
        return true;
    }
}
